package com.atguigu.headline.util;

import java.util.*;

public class ACAutomaton {
    private TrieNode root;

    public ACAutomaton() {
        root = new TrieNode();
    }

    // 构建 Trie 树
    public void buildTrie(List<String> words) {
        for (String word : words) {
            TrieNode node = root;
            int[] codePoints = word.codePoints().toArray();
            for (int i = 0; i < codePoints.length; i++) {
                int codePoint = codePoints[i];
                node = node.children.computeIfAbsent(codePoint, k -> new TrieNode());
                if (i == codePoints.length - 1) {
                    node.isEnd = true;
                    node.word = word;
                }
            }
        }
    }

    // 构建失败指针
    public void buildFailPointers() {
        Queue<TrieNode> queue = new LinkedList<>();
        root.fail = root;
        queue.add(root);

        while (!queue.isEmpty()) {
            TrieNode current = queue.poll();
            for (Map.Entry<Integer, TrieNode> entry : current.children.entrySet()) {
                int codePoint = entry.getKey();
                TrieNode child = entry.getValue();

                if (current == root) {
                    child.fail = root;
                } else {
                    TrieNode fail = current.fail;
                    while (fail != root && !fail.children.containsKey(codePoint)) {
                        fail = fail.fail;
                    }
                    if (fail.children.containsKey(codePoint)) {
                        child.fail = fail.children.get(codePoint);
                    } else {
                        child.fail = root;
                    }
                }
                queue.add(child);
            }
        }
    }

    // 多模式匹配
    public List<String> search(String text) {
        List<String> result = new ArrayList<>();
        TrieNode node = root;

        for (int codePoint : text.codePoints().toArray()) {
            while (node != root && !node.children.containsKey(codePoint)) {
                node = node.fail;
            }
            if (node.children.containsKey(codePoint)) {
                node = node.children.get(codePoint);
            } else {
                node = root;
            }

            TrieNode temp = node;
            while (temp != root) {
                if (temp.isEnd) {
                    result.add(temp.word);
                }
                temp = temp.fail;
            }
        }
        return result;
    }
}